SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Sparse matrix</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Sparse matrix</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">"Sparsity" redirects here. For other uses, see <a href="Sparse_(disambiguation)" class="mw-disambig" title="Sparse (disambiguation)">Sparse (disambiguation)</a>.</div>

<td><div class="center"><b>Example of sparse matrix</b></div>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mstyle>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left({\begin{smallmatrix}11&22&0&0&0&0&0\\0&33&44&0&0&0&0\\0&0&55&66&77&0&0\\0&0&0&0&0&88&0\\0&0&0&0&0&0&99\\\end{smallmatrix}}\right)}</annotation>

</semantics>

</math></span><img src="./6f9ffcea50d5da4133ded17f526333fdda87f702.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.369ex; margin-bottom: -0.303ex; width:20.967ex; height:8.509ex;" alt="{\displaystyle \left({\begin{smallmatrix}11&22&0&0&0&0&0\\0&33&44&0&0&0&0\\0&0&55&66&77&0&0\\0&0&0&0&0&88&0\\0&0&0&0&0&0&99\\\end{smallmatrix}}\right)}" loading="lazy"></span></div>

</td></tr>

<tr>

<td><div class="center"><span style="font-size:90%;">The above sparse matrix contains only 9 non-zero elements, with 26 zero elements. Its sparsity is 74%, and its density is 26%.</span></div>

</td></tr></tbody></table>

<p>In <a href="Numerical_analysis" title="Numerical analysis">numerical analysis</a> and <a href="Scientific_computing" class="mw-redirect" title="Scientific computing">scientific computing</a>, a <b>sparse matrix</b> or <b>sparse array</b> is a <a href="Matrix_(mathematics)" title="Matrix (mathematics)">matrix</a> in which most of the elements are zero.<sup id="cite_ref-Yan_Wu_Liu_Gao_2017_p._1-0" class="reference"><a href="#cite_note-Yan_Wu_Liu_Gao_2017_p.-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> There is no strict definition regarding the proportion of zero-value elements for a matrix to qualify as <b>sparse</b> but a common criterion is that the number of non-zero elements is roughly equal to the number of rows or columns. By contrast, if most of the elements are non-zero, the matrix is considered <b>dense</b>.<sup id="cite_ref-Yan_Wu_Liu_Gao_2017_p._1-1" class="reference"><a href="#cite_note-Yan_Wu_Liu_Gao_2017_p.-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> The number of zero-valued elements divided by the total number of elements (e.g., <i>m</i> × <i>n</i> for an <i>m</i> × <i>n</i> matrix) is sometimes referred to as the <b>sparsity</b> of the matrix.

</p><p>Conceptually, sparsity corresponds to systems with few pairwise interactions. For example, consider a line of balls connected by springs from one to the next: this is a sparse system, as only adjacent balls are coupled. By contrast, if the same line of balls were to have springs connecting each ball to all other balls, the system would correspond to a dense matrix. The concept of sparsity is useful in <a href="Combinatorics" title="Combinatorics">combinatorics</a> and application areas such as <a href="Network_theory" title="Network theory">network theory</a> and <a href="Numerical_analysis" title="Numerical analysis">numerical analysis</a>, which typically have a low density of significant data or connections. Large sparse matrices often appear in <a href="Scientific" class="mw-redirect" title="Scientific">scientific</a> or <a href="Engineering" title="Engineering">engineering</a> applications when solving <a href="Partial_differential_equation" title="Partial differential equation">partial differential equations</a>.

</p><p>When storing and manipulating sparse matrices on a <a href="Computer" title="Computer">computer</a>, it is beneficial and often necessary to use specialized <a href="Algorithm" title="Algorithm">algorithms</a> and <a href="Data_structure" title="Data structure">data structures</a> that take advantage of the sparse structure of the matrix. Specialized computers have been made for sparse matrices,<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> as they are common in the machine learning field.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> Operations using standard dense-matrix structures and algorithms are slow and inefficient when applied to large sparse matrices as processing and <a href="Computer_memory" title="Computer memory">memory</a> are wasted on the zeros. Sparse data is by nature more easily <a href="Data_compression" title="Data compression">compressed</a> and thus requires significantly less <a href="Computer_data_storage" title="Computer data storage">storage</a>. Some very large sparse matrices are infeasible to manipulate using standard dense-matrix algorithms.

</p>

<div class="mw-heading mw-heading2"><h2 id="Special_cases">Special cases</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Banded">Banded</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Band_matrix" title="Band matrix">Band matrix</a></div>

<p>A <a href="Band_matrix" title="Band matrix">band matrix</a> is a special class of sparse matrix where the non-zero elements are concentrated near the main diagonal. A band matrix is characterised by its lower and upper bandwidths, which refer to the number of diagonals below and above (respectively) the <a href="Main_diagonal" title="Main diagonal">main diagonal</a> between which all of the non-zero entries are contained.

</p><p>Formally, the <a href="Lower_bandwidth_of_a_matrix" class="mw-redirect" title="Lower bandwidth of a matrix">lower bandwidth of a matrix</a> <span class="texhtml"><b>A</b></span> is the smallest number <span class="texhtml"><i>p</i></span> such that the entry <span class="texhtml"><i>a</i><sub><i>i</i>,<i>j</i></sub></span> vanishes whenever <span class="texhtml"><i>i</i> > <i>j</i> + <i>p</i></span>. Similarly, the <a href="Band_matrix#upper_bandwidth" title="Band matrix">upper bandwidth</a> is the smallest number <span class="texhtml"><i>p</i></span> such that <span class="texhtml"><i>a</i><sub><i>i</i>,<i>j</i></sub> = 0</span> whenever <span class="texhtml"><i>i</i> < <i>j</i> − <i>p</i></span> (<a href="#CITEREFGolubVan_Loan1996">Golub & Van Loan 1996</a>, §1.2.1). For example, a <a href="Tridiagonal_matrix" title="Tridiagonal matrix">tridiagonal matrix</a> has lower bandwidth <span class="texhtml">1</span> and upper bandwidth <span class="texhtml">1</span>. As another example, the following sparse matrix has lower and upper bandwidth both equal to 3. Notice that zeros are represented with dots for clarity.

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}X&X&X&\cdot &\cdot &\cdot &\cdot &\\X&X&\cdot &X&X&\cdot &\cdot &\\X&\cdot &X&\cdot &X&\cdot &\cdot &\\\cdot &X&\cdot &X&\cdot &X&\cdot &\\\cdot &X&X&\cdot &X&X&X&\\\cdot &\cdot &\cdot &X&X&X&\cdot &\\\cdot &\cdot &\cdot &\cdot &X&\cdot &X&\\\end{bmatrix}}}</annotation>

</semantics>

</math></span></span>

</p><p>Matrices with reasonably small upper and lower bandwidth are known as band matrices and often lend themselves to simpler algorithms than general sparse matrices; or one can sometimes apply dense matrix algorithms and gain efficiency simply by looping over a reduced number of indices.

</p><p>By rearranging the rows and columns of a matrix <span class="texhtml"><b>A</b></span> it may be possible to obtain a matrix <span class="texhtml"><b>A</b>′</span> with a lower bandwidth. A number of algorithms are designed for <a href="Graph_bandwidth" title="Graph bandwidth">bandwidth minimization</a>.

</p>

<div class="mw-heading mw-heading4"><h4 id="Diagonal">Diagonal</h4></div>

<p>A diagonal matrix is the extreme case of a banded matrix, with zero upper and lower bandwidth. A diagonal matrix can be stored efficiently by storing just the entries in the <a href="Main_diagonal" title="Main diagonal">main diagonal</a> as a <a href="One-dimensional_array" class="mw-redirect" title="One-dimensional array">one-dimensional array</a>, so a diagonal <span class="texhtml"><i>n</i> × <i>n</i></span> matrix requires only <span class="texhtml"><i>n</i></span> entries in memory.

</p>

<div class="mw-heading mw-heading3"><h3 id="Symmetric">Symmetric</h3></div>

<p>A symmetric sparse matrix arises as the <a href="Adjacency_matrix" title="Adjacency matrix">adjacency matrix</a> of an <a href="Undirected_graph" class="mw-redirect" title="Undirected graph">undirected graph</a>; it can be stored efficiently as an <a href="Adjacency_list" title="Adjacency list">adjacency list</a>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Block_diagonal">Block diagonal</h3></div>

<p>A <a href="Block-diagonal_matrix" class="mw-redirect" title="Block-diagonal matrix">block-diagonal matrix</a> consists of sub-matrices along its diagonal blocks. A block-diagonal matrix <span class="texhtml"><b>A</b></span> has the form

</mrow>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {A} ={\begin{bmatrix}\mathbf {A} _{1}&0&\cdots &0\\0&\mathbf {A} _{2}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &\mathbf {A} _{n}\end{bmatrix}},}</annotation>

</semantics>

</math></span></span>

</p><p>where <span class="texhtml"><b>A</b><sub><i>k</i></sub></span> is a square matrix for all <span class="texhtml"><i>k</i> = 1, ..., <i>n</i></span>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Reducing_fill-in">Reducing fill-in</h3></div>

<p>The <i>fill-in</i> of a matrix are those entries that change from an initial zero to a non-zero value during the execution of an algorithm. To reduce the memory requirements and the number of arithmetic operations used during an algorithm, it is useful to minimize the fill-in by switching rows and columns in the matrix. The <a href="Symbolic_Cholesky_decomposition" title="Symbolic Cholesky decomposition">symbolic Cholesky decomposition</a> can be used to calculate the worst possible fill-in before doing the actual <a href="Cholesky_decomposition" title="Cholesky decomposition">Cholesky decomposition</a>.

</p><p>There are other methods than the <a href="Cholesky_decomposition" title="Cholesky decomposition">Cholesky decomposition</a> in use. Orthogonalization methods (such as QR factorization) are common, for example, when solving problems by least squares methods. While the theoretical fill-in is still the same, in practical terms the "false non-zeros" can be different for different methods. And symbolic versions of those algorithms can be used in the same manner as the symbolic Cholesky to compute worst case fill-in.

</p>

<div class="mw-heading mw-heading3"><h3 id="Solving_sparse_matrix_equations">Solving sparse matrix equations</h3></div>

<p>Both <a href="Iterative_method" title="Iterative method">iterative</a> and direct methods exist for sparse matrix solving.

</p><p>Iterative methods, such as <a href="Conjugate_gradient" class="mw-redirect" title="Conjugate gradient">conjugate gradient</a> method and <a href="GMRES" class="mw-redirect" title="GMRES">GMRES</a> utilize fast computations of matrix-vector products <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Ax_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Ax_{i}}</annotation>

</semantics>

</math></span><img src="./9a268eb5b5f04010ae93a8f69d069b91dad1f11e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.872ex; height:2.509ex;" alt="{\displaystyle Ax_{i}}" loading="lazy"></span>, where matrix <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math></span><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> is sparse. The use of <a href="Preconditioner" title="Preconditioner">preconditioners</a> can significantly accelerate convergence of such iterative methods.

</p>

<div class="mw-heading mw-heading2"><h2 id="Storage"> Storage</h2></div>

<p>A matrix is typically stored as a two-dimensional array. Each entry in the array represents an element <span class="texhtml"><i>a</i><sub><i>i</i>,<i>j</i></sub></span> of the matrix and is accessed by the two <a href="Array_data_structure" class="mw-redirect" title="Array data structure">indices</a> <span class="texhtml"><i>i</i></span> and <span class="texhtml"><i>j</i></span>. Conventionally, <span class="texhtml"><i>i</i></span> is the row index, numbered from top to bottom, and <span class="texhtml"><i>j</i></span> is the column index, numbered from left to right. For an <span class="texhtml"><i>m</i> × <i>n</i></span> matrix, the amount of memory required to store the matrix in this format is proportional to <span class="texhtml"><i>m</i> × <i>n</i></span> (disregarding the fact that the dimensions of the matrix also need to be stored).

</p><p>In the case of a sparse matrix, substantial memory requirement reductions can be realized by storing only the non-zero entries. Depending on the number and distribution of the non-zero entries, different data structures can be used and yield huge savings in memory when compared to the basic approach. The trade-off is that accessing the individual elements becomes more complex and additional structures are needed to be able to recover the original matrix unambiguously.

</p><p>Formats can be divided into two groups:

</p>

<ul><li>Those that support efficient modification, such as DOK (Dictionary of keys), LIL (List of lists), or COO (Coordinate list). These are typically used to construct the matrices.</li>

<li>Those that support efficient access and matrix operations, such as CSR (Compressed Sparse Row) or CSC (Compressed Sparse Column).</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Dictionary_of_keys_(DOK)">Dictionary of keys (DOK)</h3></div>

<p>DOK consists of a <a href="Associative_array" title="Associative array">dictionary</a> that maps <span class="texhtml">(row, column)</span>-<a href="Ordered_pair" title="Ordered pair">pairs</a> to the value of the elements. Elements that are missing from the dictionary are taken to be zero. The format is good for incrementally constructing a sparse matrix in random order, but poor for iterating over non-zero values in lexicographical order. One typically constructs a matrix in this format and then converts to another more efficient format for processing.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="List_of_lists_(LIL)">List of lists (LIL)</h3></div>

<p>LIL stores one list per row, with each entry containing the column index and the value. Typically, these entries are kept sorted by column index for faster lookup. This is another format good for incremental matrix construction.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Coordinate_list_(COO)">Coordinate list (COO)</h3></div>

<p>COO stores a list of <span class="texhtml">(row, column, value)</span> tuples. Ideally, the entries are sorted first by row index and then by column index, to improve random access times. This is another format that is good for incremental matrix construction.<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Compressed_sparse_row_(CSR,_CRS_or_Yale_format)">Compressed sparse row (CSR, CRS or Yale format)</h3></div>

<p>The <i>compressed sparse row</i> (CSR) or <i>compressed row storage</i> (CRS) or Yale format represents a matrix <span class="texhtml"><b>M</b></span> by three (one-dimensional) arrays, that respectively contain nonzero values, the extents of rows, and column indices. It is similar to COO, but compresses the row indices, hence the name. This format allows fast row access and matrix-vector multiplications (<span class="texhtml"><b>M</b><i>x</i></span>). The CSR format has been in use since at least the mid-1960s, with the first complete description appearing in 1967.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup>

</p><p>The CSR format stores a sparse <span class="texhtml"><i>m</i> × <i>n</i></span> matrix <span class="texhtml"><b>M</b></span> in row form using three (one-dimensional) arrays <span class="texhtml">(V, COL_INDEX, ROW_INDEX)</span>. Let <span class="texhtml">NNZ</span> denote the number of nonzero entries in <span class="texhtml"><b>M</b></span>. (Note that <a href="Zero-based_numbering" title="Zero-based numbering">zero-based indices</a> shall be used here.)

</p>

<ul><li>The arrays <span class="texhtml">V</span> and <span class="texhtml">COL_INDEX</span> are of length <span class="texhtml">NNZ</span>, and contain the non-zero values and the column indices of those values respectively</li>

<li><span class="texhtml">COL_INDEX</span> contains the column in which the corresponding entry <span class="texhtml">V</span> is located.</li>

<li>The array <span class="texhtml">ROW_INDEX</span> is of length <span class="texhtml"><i>m</i> + 1</span> and encodes the index in <span class="texhtml">V</span> and <span class="texhtml">COL_INDEX</span> where the given row starts. This is equivalent to <span class="texhtml">ROW_INDEX[j]</span> encoding the total number of nonzeros above row <span class="texhtml">j</span>. The last element is <span class="texhtml">NNZ</span> , i.e., the fictitious index in <span class="texhtml">V</span> immediately after the last valid index <span class="texhtml">NNZ − 1</span>.<sup id="cite_ref-Saad03_8-0" class="reference"><a href="#cite_note-Saad03-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup></li></ul>

<p>For example, the matrix

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{pmatrix}5&0&0&0\\0&8&0&0\\0&0&3&0\\0&6&0&0\\\end{pmatrix}}}</annotation>

</semantics>

</math></span></span>

is a <span class="texhtml">4 × 4</span> matrix with 4 nonzero elements, hence

</p>

<pre>V = [ 5 8 3 6 ]

COL_INDEX = [ 0 1 2 1 ]

ROW_INDEX = [ 0 1 2 3 4 ]

</pre>

<p>assuming a zero-indexed language.

</p><p>To extract a row, we first define:

</p>

<pre>row_start = ROW_INDEX[row]

row_end = ROW_INDEX[row + 1]

</pre>

<p>Then we take slices from V and COL_INDEX starting at row_start and ending at row_end.

</p><p>To extract the row 1 (the second row) of this matrix we set <code>row_start=1</code> and <code>row_end=2</code>. Then we make the slices <code>V[1:2] = [8]</code> and <code>COL_INDEX[1:2] = [1]</code>. We now know that in row 1 we have one element at column 1 with value 8.

</p><p>In this case the CSR representation contains 13 entries, compared to 16 in the original matrix. The CSR format saves on memory only when <span class="texhtml">NNZ < (<i>m</i> (<i>n</i> − 1) − 1) / 2</span>.

</p><p>Another example, the matrix

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{pmatrix}10&20&0&0&0&0\\0&30&0&40&0&0\\0&0&50&60&70&0\\0&0&0&0&0&80\\\end{pmatrix}}}</annotation>

</semantics>

</math></span></span>

is a <span class="texhtml">4 × 6</span> matrix (24 entries) with 8 nonzero elements, so

</p>

<pre>V = [ 10 20 30 40 50 60 70 80 ]

COL_INDEX = [ 0 1 1 3 2 3 4 5 ]

ROW_INDEX = [ 0 2 4 7 8 ]

</pre>

<p>The whole is stored as 21 entries: 8 in <span class="texhtml">V</span>, 8 in <span class="texhtml">COL_INDEX</span>, and 5 in <span class="texhtml">ROW_INDEX</span>.

</p>

<ul><li><span class="texhtml">ROW_INDEX</span> splits the array <span class="texhtml">V</span> into rows: <code>(10, 20) (30, 40) (50, 60, 70) (80)</code>, indicating the index of <span class="texhtml">V</span> (and <span class="texhtml">COL_INDEX</span>) where each row starts and ends;</li>

<li><span class="texhtml">COL_INDEX</span> aligns values in columns: <code>(10, 20, ...) (0, 30, 0, 40, ...)(0, 0, 50, 60, 70, 0) (0, 0, 0, 0, 0, 80)</code>.</li></ul>

<p>Note that in this format, the first value of <span class="texhtml">ROW_INDEX</span> is always zero and the last is always <span class="texhtml">NNZ</span>, so they are in some sense redundant (although in programming languages where the array length needs to be explicitly stored, <span class="texhtml">NNZ</span> would not be redundant). Nonetheless, this does avoid the need to handle an exceptional case when computing the length of each row, as it guarantees the formula <span class="texhtml">ROW_INDEX[<i>i</i> + 1] − ROW_INDEX[<i>i</i>]</span> works for any row <span class="texhtml"><i>i</i></span>. Moreover, the memory cost of this redundant storage is likely insignificant for a sufficiently large matrix.

</p><p>The (old and new) Yale sparse matrix formats are instances of the CSR scheme. The old Yale format works exactly as described above, with three arrays; the new format combines <span class="texhtml">ROW_INDEX</span> and <span class="texhtml">COL_INDEX</span> into a single array and handles the diagonal of the matrix separately.<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup>

</p><p>For <a href="Logical_matrix" title="Logical matrix"> logical</a> <a href="Adjacency_matrix" title="Adjacency matrix"> adjacency matrices</a>, the data array can be omitted, as the existence of an entry in the row array is sufficient to model a binary adjacency relation.

</p><p>It is likely known as the Yale format because it was proposed in the 1977 Yale Sparse Matrix Package report from Department of Computer Science at Yale University.<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Compressed_sparse_column_(CSC_or_CCS)">Compressed sparse column (CSC or CCS)</h3></div>

<p>CSC is similar to CSR except that values are read first by column, a row index is stored for each value, and column pointers are stored. For example, CSC is <span class="texhtml">(val, row_ind, col_ptr)</span>, where <span class="texhtml">val</span> is an array of the (top-to-bottom, then left-to-right) non-zero values of the matrix; <span class="texhtml">row_ind</span> is the row indices corresponding to the values; and, <span class="texhtml">col_ptr</span> is the list of <span class="texhtml">val</span> indexes where each column starts. The name is based on the fact that column index information is compressed relative to the COO format. One typically uses another format (LIL, DOK, COO) for construction. This format is efficient for arithmetic operations, column slicing, and matrix-vector products. This is the traditional format for specifying a sparse matrix in MATLAB (via the <code>sparse</code> function).

</p>

<div class="mw-heading mw-heading2"><h2 id="Software">Software</h2></div>

<p>Many software libraries support sparse matrices, and provide solvers for sparse matrix equations. The following are open-source:

</p>

<ul><li><a href="Portable%2C_Extensible_Toolkit_for_Scientific_Computation" title="Portable, Extensible Toolkit for Scientific Computation">PETSc</a>, a large C library, containing many different matrix solvers for a variety of matrix storage formats.</li>

<li><a href="Trilinos" title="Trilinos">Trilinos</a>, a large C++ library, with sub-libraries dedicated to the storage of dense and sparse matrices and solution of corresponding linear systems.</li>

<li><a href="Eigen_(C%2B%2B_library)" title="Eigen (C++ library)">Eigen3</a> is a C++ library that contains several sparse matrix solvers. However, none of them are <a href="Parallel_computing" title="Parallel computing">parallelized</a>.</li>

<li><a href="MUMPS_(software)" title="MUMPS (software)">MUMPS</a> (<b>MU</b>ltifrontal <b>M</b>assively <b>P</b>arallel sparse direct <b>S</b>olver), written in Fortran90, is a <a href="Frontal_solver" title="Frontal solver">frontal solver</a>.</li>

<li><a href="Deal.II" title="Deal.II">deal.II</a>, a finite element library that also has a sub-library for sparse linear systems and their solution.</li>

<li><a href="Dune_(mathematics_software)" title="Dune (mathematics software)">DUNE</a>, another finite element library that also has a sub-library for sparse linear systems and their solution.</li>

<li><a href="Armadillo_(C%2B%2B_library)" title="Armadillo (C++ library)">Armadillo</a> provides a user-friendly C++ wrapper for BLAS and LAPACK.</li>

<li><a href="SciPy" title="SciPy">SciPy</a> provides support for several sparse matrix formats, linear algebra, and solvers.</li>

<li><a href="ALGLIB" title="ALGLIB">ALGLIB</a> is a C++ and C# library with sparse linear algebra support</li>

<li><a href="ARPACK" title="ARPACK">ARPACK</a> Fortran 77 library for sparse matrix diagonalization and manipulation, using the Arnoldi algorithm</li>

<li><a href="SLEPc" title="SLEPc">SLEPc</a> Library for solution of large scale linear systems and sparse matrices</li>

<li><a href="Scikit-learn" title="Scikit-learn">scikit-learn</a>, a Python library for <a href="Machine_learning" title="Machine learning">machine learning</a>, provides support for sparse matrices and solvers</li>

<li><a rel="nofollow" class="external text" href="https://docs.julialang.org/en/v1/stdlib/SparseArrays/">SparseArrays</a> is a <a href="Julia_(programming_language)" title="Julia (programming language)">Julia</a> standard library.</li>

<li>PSBLAS, software toolkit to solve sparse linear systems supporting multiple formats also on GPU.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

<p>The term <i>sparse matrix</i> was possibly coined by <a href="Harry_Markowitz" title="Harry Markowitz">Harry Markowitz</a> who initiated some pioneering work but then left the field.<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup>

</p>

/* start https://en.wikipedia.org/ */

.mw-parser-output .div-col{margin-top:0.3em;column-width:30em}.mw-parser-output .div-col-small{font-size:90%}.mw-parser-output .div-col-rules{column-rule:1px solid #aaa}.mw-parser-output .div-col dl,.mw-parser-output .div-col ol,.mw-parser-output .div-col ul{margin-top:0}.mw-parser-output .div-col li,.mw-parser-output .div-col dd{page-break-inside:avoid;break-inside:avoid-column}

/* end https://en.wikipedia.org/ */

</style><div class="div-col" style="column-width: 22em;">

<ul><li><a href="Matrix_representation" title="Matrix representation">Matrix representation</a></li>

<li><a href="Pareto_principle" title="Pareto principle">Pareto principle</a></li>

<li><a href="Ragged_matrix" class="mw-redirect" title="Ragged matrix">Ragged matrix</a></li>

<li><a href="Single-entry_matrix" class="mw-redirect" title="Single-entry matrix">Single-entry matrix</a></li>

<li><a href="Skyline_matrix" title="Skyline matrix">Skyline matrix</a></li>

<li><a href="Sparse_graph_code" title="Sparse graph code">Sparse graph code</a></li>

<li><a href="Sparse_file" title="Sparse file">Sparse file</a></li>

<li><a href="Harwell-Boeing_file_format" title="Harwell-Boeing file format">Harwell-Boeing file format</a></li>

<li><a href="Matrix_Market_exchange_formats" title="Matrix Market exchange formats">Matrix Market exchange formats</a></li></ul></div>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFYanWuLiuGao2017" class="citation conference cs1">Yan, Di; Wu, Tao; Liu, Ying; Gao, Yang (2017). "An efficient sparse-dense matrix multiplication on a multicore system". <i>2017 IEEE 17th International Conference on Communication Technology (ICCT)</i>. IEEE. pp. <span class="nowrap">1880–</span>3. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2Ficct.2017.8359956">10.1109/icct.2017.8359956</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-5090-3944-9</bdi>. <q>The computation kernel of DNN is large sparse-dense matrix multiplication. In the field of numerical analysis, a sparse matrix is a matrix populated primarily with zeros as elements of the table. By contrast, if the number of non-zero elements in a matrix is relatively large, then it is commonly considered a dense matrix. The fraction of zero elements (non-zero elements) in a matrix is called the sparsity (density). Operations using standard dense-matrix structures and algorithms are relatively slow and consume large amounts of memory when applied to large sparse matrices.</q></cite></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.businesswire.com/news/home/20190819005148/en/Cerebras-Systems-Unveils-Industry%E2%80%99s-Trillion-Transistor-Chip">"Cerebras Systems Unveils the Industry's First Trillion Transistor Chip"</a>. <i>www.businesswire.com</i>. 2019-08-19<span class="reference-accessdate">. Retrieved <span class="nowrap">2019-12-02</span></span>. <q>The WSE contains 400,000 AI-optimized compute cores. Called SLAC™ for Sparse Linear Algebra Cores, the compute cores are flexible, programmable, and optimized for the sparse linear algebra that underpins all neural network computation</q></cite></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite class="citation pressrelease cs1"><a rel="nofollow" class="external text" href="https://www.anl.gov/article/argonne-national-laboratory-deploys-cerebras-cs1-the-worlds-fastest-artificial-intelligence-computer">"Argonne National Laboratory Deploys Cerebras CS-1, the World's Fastest Artificial Intelligence Computer | Argonne National Laboratory"</a>. <i>www.anl.gov</i> (Press release)<span class="reference-accessdate">. Retrieved <span class="nowrap">2019-12-02</span></span>. <q>The WSE is the largest chip ever made at 46,225 square millimeters in area, it is 56.7 times larger than the largest graphics processing unit. It contains 78 times more AI optimized compute cores, 3,000 times more high speed, on-chip memory, 10,000 times more memory bandwidth, and 33,000 times more communication bandwidth.</q></cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text">See <a rel="nofollow" class="external text" href="http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.dok_matrix.html"><code>scipy.sparse.dok_matrix</code></a></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text">See <a rel="nofollow" class="external text" href="http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.lil_matrix.html"><code>scipy.sparse.lil_matrix</code></a></span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text">See <a rel="nofollow" class="external text" href="http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.coo_matrix.html"><code>scipy.sparse.coo_matrix</code></a></span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><cite id="CITEREFBuluçFinemanFrigoGilbert2009" class="citation conference cs1">Buluç, Aydın; Fineman, Jeremy T.; Frigo, Matteo; Gilbert, John R.; <a href="Charles_E._Leiserson" title="Charles E. Leiserson">Leiserson, Charles E.</a> (2009). <a rel="nofollow" class="external text" href="https://people.eecs.berkeley.edu/~aydin/csb2009.pdf"><i>Parallel sparse matrix-vector and matrix-transpose-vector multiplication using compressed sparse blocks</i></a> <span class="cs1-format">(PDF)</span>. ACM Symp. on Parallelism in Algorithms and Architectures. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.211.5256">10.1.1.211.5256</a></span>.</cite></span>

</li>

</li>

<li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><cite id="CITEREFBankDouglas1993" class="citation cs2">Bank, Randolph E.; Douglas, Craig C. (1993), <a rel="nofollow" class="external text" href="http://www.mgnet.org/~douglas/Preprints/pub0034.pdf">"Sparse Matrix Multiplication Package (SMMP)"</a> <span class="cs1-format">(PDF)</span>, <i>Advances in Computational Mathematics</i>, <b>1</b>: <span class="nowrap">127–</span>137, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF02070824">10.1007/BF02070824</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:6412241">6412241</a></cite></span>

</li>

<li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><cite id="CITEREFEisenstatGurskySchultzSherman1977" class="citation web cs1">Eisenstat, S. C.; Gursky, M. C.; Schultz, M. H.; Sherman, A. H. (April 1977). <a rel="nofollow" class="external text" href="https://apps.dtic.mil/dtic/tr/fulltext/u2/a047724.pdf">"Yale Sparse Matrix Package"</a> <span class="cs1-format">(PDF)</span>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20190406045412/https://apps.dtic.mil/dtic/tr/fulltext/u2/a047724.pdf">Archived</a> <span class="cs1-format">(PDF)</span> from the original on April 6, 2019<span class="reference-accessdate">. Retrieved <span class="nowrap">6 April</span> 2019</span>.</cite></span>

</li>

<li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="http://purl.umn.edu/107467">Oral history interview with Harry M. Markowitz</a>, pp. 9, 10.</span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .refbegin{margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li{margin-left:0;padding-left:3.2em;text-indent:-3.2em}.mw-parser-output .refbegin-hanging-indents ul,.mw-parser-output .refbegin-hanging-indents ul li{list-style:none}@media(max-width:720px){.mw-parser-output .refbegin-hanging-indents>ul>li{padding-left:1.6em;text-indent:-1.6em}}.mw-parser-output .refbegin-columns{margin-top:0.3em}.mw-parser-output .refbegin-columns ul{margin-top:0}.mw-parser-output .refbegin-columns li{page-break-inside:avoid;break-inside:avoid-column}@media screen{.mw-parser-output .refbegin{font-size:90%}}

/* end https://en.wikipedia.org/ */

</style><div class="refbegin" style="">

<ul><li><cite id="CITEREFGolubVan_Loan1996" class="citation book cs1"><a href="Gene_H._Golub" title="Gene H. Golub">Golub, Gene H.</a>; <a href="Charles_F._Van_Loan" title="Charles F. Van Loan">Van Loan, Charles F.</a> (1996). <i>Matrix Computations</i> (3rd ed.). Baltimore: Johns Hopkins. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-8018-5414-9</bdi>.</cite></li>

<li><cite id="CITEREFStoerBulirsch2002" class="citation book cs1">Stoer, Josef; Bulirsch, Roland (2002). <i>Introduction to Numerical Analysis</i> (3rd ed.). Springer. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-0-387-21738-3">10.1007/978-0-387-21738-3</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-387-95452-3</bdi>.</cite></li>

<li><cite id="CITEREFTewarson1973" class="citation book cs1">Tewarson, Reginald P. (1973). <a rel="nofollow" class="external text" href="https://www.sciencedirect.com/science/book/9780126856507"><i>Sparse Matrices</i></a>. Mathematics in science and engineering. Vol. 99. Academic Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-12-685650-8</bdi>. <a href="OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/316552948">316552948</a>.</cite> (This book, by a professor at the State University of New York at Stony Book, was the first book exclusively dedicated to Sparse Matrices. Graduate courses using this as a textbook were offered at that University in the early 1980s).</li>

<li><cite id="CITEREFBankDouglas" class="citation web cs1">Bank, Randolph E.; Douglas, Craig C. <a rel="nofollow" class="external text" href="http://www.mgnet.org/~douglas/Preprints/pub0034.pdf">"Sparse Matrix Multiplication Package"</a> <span class="cs1-format">(PDF)</span>.</cite></li>

<li><cite id="CITEREFPissanetzky1984" class="citation book cs1">Pissanetzky, Sergio (1984). <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/sparsematrixtech0000piss"><i>Sparse Matrix Technology</i></a></span>. Academic Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-12-557580-5</bdi>. <a href="OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/680489638">680489638</a>.</cite></li>

<li><cite id="CITEREFSnay1976" class="citation journal cs1">Snay, Richard A. (1976). "Reducing the profile of sparse symmetric matrices". <i><a href="Bulletin_G%C3%A9od%C3%A9sique" class="mw-redirect" title="Bulletin Géodésique">Bulletin Géodésique</a></i>. <b>50</b> (4): <span class="nowrap">341–</span>352. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1976BGeod..50..341S">1976BGeod..50..341S</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF02521587">10.1007/BF02521587</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://hdl.handle.net/2027%2Fuc1.31210024848523">2027/uc1.31210024848523</a></span>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:123079384">123079384</a>.</cite> Also NOAA Technical Memorandum NOS NGS-4, National Geodetic Survey, Rockville, MD. Referencing <a href="#CITEREFSaad2003">Saad 2003</a>.</li>

<li><cite id="CITEREFScottTuma2023" class="citation book cs1">Scott, Jennifer; Tuma, Miroslav (2023). <i>Algorithms for Sparse Linear Systems</i>. Nečas Center Series. Birkhauser. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-031-25820-6">10.1007/978-3-031-25820-6</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-031-25819-0</bdi>.</cite> (Open Access)</li></ul>

</div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite id="CITEREFGibbsPooleStockmeyer1976" class="citation journal cs1">Gibbs, Norman E.; Poole, William G.; Stockmeyer, Paul K. (1976). <span class="id-lock-subscription" title="Paid subscription required"><a rel="nofollow" class="external text" href="http://portal.acm.org/citation.cfm?id=355707">"A comparison of several bandwidth and profile reduction algorithms"</a></span>. <i>ACM Transactions on Mathematical Software</i>. <b>2</b> (4): <span class="nowrap">322–</span>330. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F355705.355707">10.1145/355705.355707</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:14494429">14494429</a>.</cite></li>

<li><cite id="CITEREFGilbertMolerSchreiber1992" class="citation journal cs1">Gilbert, John R.; Moler, Cleve; Schreiber, Robert (1992). <a rel="nofollow" class="external text" href="http://citeseer.ist.psu.edu/gilbert91sparse.html">"Sparse matrices in MATLAB: Design and Implementation"</a>. <i>SIAM Journal on Matrix Analysis and Applications</i>. <b>13</b> (1): <span class="nowrap">333–</span>356. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.470.1054">10.1.1.470.1054</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0613024">10.1137/0613024</a>.</cite></li>

<li><a rel="nofollow" class="external text" href="http://faculty.cse.tamu.edu/davis/research.html">Sparse Matrix Algorithms Research</a> at the Texas A&M University.</li>

<li><a rel="nofollow" class="external text" href="https://sparse.tamu.edu/">SuiteSparse Matrix Collection</a></li>

<li><a rel="nofollow" class="external text" href="http://www.small-project.eu">SMALL project</a> A EU-funded project on sparse models, algorithms and dictionary learning for large-scale data.</li>

<li><cite id="CITEREFHackbusch2016" class="citation book cs1">Hackbusch, Wolfgang (2016). <i>Iterative Solution of Large Sparse Systems of Equations</i>. Applied Mathematical Sciences. Vol. 95 (2nd ed.). Springer. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-319-28483-5">10.1007/978-3-319-28483-5</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-319-28481-1</bdi>.</cite></li>

<li><cite id="CITEREFSaad2003" class="citation book cs1">Saad, Yousef (2003). <i>Iterative Methods for Sparse Linear Systems</i>. SIAM. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F1.9780898718003">10.1137/1.9780898718003</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-89871-534-7</bdi>. <a href="OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/693784152">693784152</a>.</cite></li>

<li><cite id="CITEREFDavis2006" class="citation book cs1">Davis, Timothy A. (2006). <i>Direct Methods for Sparse Linear Systems</i>. SIAM. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F1.9780898718881">10.1137/1.9780898718881</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-89871-613-9</bdi>. <a href="OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/694087302">694087302</a>.</cite></li></ul>

</div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Data_structures216" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Data_structures216" style="font-size:114%;margin:0 4em"><a href="Data_structure" title="Data structure">Data structures</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Types</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Collection_(abstract_data_type)" title="Collection (abstract data type)">Collection</a></li>

<li><a href="Container_(abstract_data_type)" title="Container (abstract data type)">Container</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Abstract_data_type" title="Abstract data type">Abstract</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Associative_array" title="Associative array">Associative array</a>

<ul><li><a href="Multimap" title="Multimap">Multimap</a></li>

<li><a href="Retrieval_Data_Structure" title="Retrieval Data Structure">Retrieval Data Structure</a></li></ul></li>

<li><a href="Stack_(abstract_data_type)" title="Stack (abstract data type)">Stack</a></li>

<li><a href="Queue_(abstract_data_type)" title="Queue (abstract data type)">Queue</a>

<ul><li><a href="Double-ended_queue" title="Double-ended queue">Double-ended queue</a></li></ul></li>

<li><a href="Priority_queue" title="Priority queue">Priority queue</a>

<ul><li><a href="Double-ended_priority_queue" title="Double-ended priority queue">Double-ended priority queue</a></li></ul></li>

<ul><li><a href="Set_(abstract_data_type)#Multiset" title="Set (abstract data type)">Multiset</a></li>

<li><a href="Disjoint-set_data_structure" title="Disjoint-set data structure">Disjoint-set</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Array_(data_structure)" title="Array (data structure)">Arrays</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bit_array" title="Bit array">Bit array</a></li>

<li><a href="Circular_buffer" title="Circular buffer">Circular buffer</a></li>

<li><a href="Dynamic_array" title="Dynamic array">Dynamic array</a></li>

<li><a href="Hash_table" title="Hash table">Hash table</a></li>

<li><a href="Hashed_array_tree" title="Hashed array tree">Hashed array tree</a></li>

</ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Linked_data_structure" title="Linked data structure">Linked</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Association_list" title="Association list">Association list</a></li>

<li><a href="Linked_list" title="Linked list">Linked list</a></li>

<li><a href="Unrolled_linked_list" title="Unrolled linked list">Unrolled linked list</a></li>

<li><a href="XOR_linked_list" title="XOR linked list">XOR linked list</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Tree_(data_structure)" class="mw-redirect" title="Tree (data structure)">Trees</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Binary_search_tree" title="Binary search tree">Binary search tree</a>

<li><a href="Red%E2%80%93black_tree" title="Red–black tree">Red–black tree</a></li>

<li><a href="Self-balancing_binary_search_tree" title="Self-balancing binary search tree">Self-balancing tree</a></li>

<li><a href="Splay_tree" title="Splay tree">Splay tree</a></li></ul></li>

<ul><li><a href="Binary_heap" title="Binary heap">Binary heap</a></li>

<li><a href="Binomial_heap" title="Binomial heap">Binomial heap</a></li>

<li><a href="Fibonacci_heap" title="Fibonacci heap">Fibonacci heap</a></li></ul></li>

<li><a href="Hilbert_R-tree" title="Hilbert R-tree">Hilbert R-tree</a></li></ul></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Graph_(abstract_data_type)" title="Graph (abstract data type)">Graphs</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Binary_decision_diagram" title="Binary decision diagram">Binary decision diagram</a></li>

<li><a href="Directed_acyclic_graph" title="Directed acyclic graph">Directed acyclic graph</a></li>

<li><a href="Deterministic_acyclic_finite_state_automaton" title="Deterministic acyclic finite state automaton">Directed acyclic word graph</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div>

<ul><li><a href="List_of_data_structures" title="List of data structures">List of data structures</a></li></ul>

</div></td></tr></tbody></table></div>

<div class="navbox-styles"></div><div role="navigation" class="navbox" aria-labelledby="Matrix_classes596" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Matrix_classes596" style="font-size:114%;margin:0 4em"><a href="Matrix_(mathematics)" title="Matrix (mathematics)">Matrix</a> classes</div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Explicitly constrained entries</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Alternant_matrix" title="Alternant matrix">Alternant</a></li>

<li><a href="Anti-diagonal_matrix" title="Anti-diagonal matrix">Anti-diagonal</a></li>

<li><a href="Skew-Hermitian_matrix" title="Skew-Hermitian matrix">Anti-Hermitian</a></li>

<li><a href="Skew-symmetric_matrix" title="Skew-symmetric matrix">Anti-symmetric</a></li>

<li><a href="Arrowhead_matrix" title="Arrowhead matrix">Arrowhead</a></li>

<li><a href="Bidiagonal_matrix" title="Bidiagonal matrix">Bidiagonal</a></li>

<li><a href="Bisymmetric_matrix" title="Bisymmetric matrix">Bisymmetric</a></li>

<li><a href="Block-diagonal_matrix" class="mw-redirect" title="Block-diagonal matrix">Block-diagonal</a></li>

<li><a href="Block_matrix" title="Block matrix">Block</a></li>

<li><a href="Block_tridiagonal_matrix" class="mw-redirect" title="Block tridiagonal matrix">Block tridiagonal</a></li>

<li><a href="Boolean_matrix" title="Boolean matrix">Boolean</a></li>

<li><a href="Cauchy_matrix" title="Cauchy matrix">Cauchy</a></li>

<li><a href="Centrosymmetric_matrix" title="Centrosymmetric matrix">Centrosymmetric</a></li>

<li><a href="Conference_matrix" title="Conference matrix">Conference</a></li>

<li><a href="Complex_Hadamard_matrix" title="Complex Hadamard matrix">Complex Hadamard</a></li>

<li><a href="Copositive_matrix" title="Copositive matrix">Copositive</a></li>

<li><a href="Diagonally_dominant_matrix" title="Diagonally dominant matrix">Diagonally dominant</a></li>

<li><a href="Diagonal_matrix" title="Diagonal matrix">Diagonal</a></li>

<li><a href="DFT_matrix" title="DFT matrix">Discrete Fourier Transform</a></li>

<li><a href="Elementary_matrix" title="Elementary matrix">Elementary</a></li>

<li><a href="Equivalent_matrix" class="mw-redirect" title="Equivalent matrix">Equivalent</a></li>

<li><a href="Frobenius_matrix" title="Frobenius matrix">Frobenius</a></li>

<li><a href="Generalized_permutation_matrix" title="Generalized permutation matrix">Generalized permutation</a></li>

<li><a href="Hadamard_matrix" title="Hadamard matrix">Hadamard</a></li>

<li><a href="Hankel_matrix" title="Hankel matrix">Hankel</a></li>

<li><a href="Hermitian_matrix" title="Hermitian matrix">Hermitian</a></li>

<li><a href="Hessenberg_matrix" title="Hessenberg matrix">Hessenberg</a></li>

<li><a href="Hollow_matrix" title="Hollow matrix">Hollow</a></li>

<li><a href="Integer_matrix" title="Integer matrix">Integer</a></li>

<li><a href="Logical_matrix" title="Logical matrix">Logical</a></li>

<li><a href="Matrix_unit" title="Matrix unit">Matrix unit</a></li>

<li><a href="Metzler_matrix" title="Metzler matrix">Metzler</a></li>

<li><a href="Moore_matrix" title="Moore matrix">Moore</a></li>

<li><a href="Nonnegative_matrix" title="Nonnegative matrix">Nonnegative</a></li>

<li><a href="Pentadiagonal_matrix" class="mw-redirect" title="Pentadiagonal matrix">Pentadiagonal</a></li>

<li><a href="Permutation_matrix" title="Permutation matrix">Permutation</a></li>

<li><a href="Persymmetric_matrix" title="Persymmetric matrix">Persymmetric</a></li>

<li><a href="Polynomial_matrix" title="Polynomial matrix">Polynomial</a></li>

<li><a href="Quaternionic_matrix" title="Quaternionic matrix">Quaternionic</a></li>

<li><a href="Signature_matrix" title="Signature matrix">Signature</a></li>

<li><a href="Skew-Hermitian_matrix" title="Skew-Hermitian matrix">Skew-Hermitian</a></li>

<li><a href="Skew-symmetric_matrix" title="Skew-symmetric matrix">Skew-symmetric</a></li>

<li><a href="Skyline_matrix" title="Skyline matrix">Skyline</a></li>

<li><a href="Sylvester_matrix" title="Sylvester matrix">Sylvester</a></li>

<li><a href="Symmetric_matrix" title="Symmetric matrix">Symmetric</a></li>

<li><a href="Toeplitz_matrix" title="Toeplitz matrix">Toeplitz</a></li>

<li><a href="Triangular_matrix" title="Triangular matrix">Triangular</a></li>

<li><a href="Tridiagonal_matrix" title="Tridiagonal matrix">Tridiagonal</a></li>

<li><a href="Vandermonde_matrix" title="Vandermonde matrix">Vandermonde</a></li>

<li><a href="Walsh_matrix" title="Walsh matrix">Walsh</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Constant</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Exchange_matrix" title="Exchange matrix">Exchange</a></li>

<li><a href="Hilbert_matrix" title="Hilbert matrix">Hilbert</a></li>

<li><a href="Identity_matrix" title="Identity matrix">Identity</a></li>

<li><a href="Lehmer_matrix" title="Lehmer matrix">Lehmer</a></li>

<li><a href="Pascal_matrix" title="Pascal matrix">Pascal</a></li>

<li><a href="Pauli_matrices" title="Pauli matrices">Pauli</a></li>

<li><a href="Redheffer_matrix" title="Redheffer matrix">Redheffer</a></li>

<li><a href="Shift_matrix" title="Shift matrix">Shift</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Conditions on <a href="Eigenvalues_and_eigenvectors" title="Eigenvalues and eigenvectors">eigenvalues or eigenvectors</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Companion_matrix" title="Companion matrix">Companion</a></li>

<li><a href="Convergent_matrix" title="Convergent matrix">Convergent</a></li>

<li><a href="Defective_matrix" title="Defective matrix">Defective</a></li>

<li><a href="Definite_matrix" title="Definite matrix">Definite</a></li>

<li><a href="Diagonalizable_matrix" title="Diagonalizable matrix">Diagonalizable</a></li>

<li><a href="Hurwitz-stable_matrix" title="Hurwitz-stable matrix">Hurwitz-stable</a></li>

<li><a href="Positive-definite_matrix" class="mw-redirect" title="Positive-definite matrix">Positive-definite</a></li>

<li><a href="Stieltjes_matrix" title="Stieltjes matrix">Stieltjes</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Satisfying conditions on <a href="Matrix_product" class="mw-redirect" title="Matrix product">products</a> or <a href="Inverse_of_a_matrix" class="mw-redirect" title="Inverse of a matrix">inverses</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Matrix_congruence" title="Matrix congruence">Congruent</a></li>

<li><a href="Idempotent_matrix" title="Idempotent matrix">Idempotent</a> or <a href="Projection_(linear_algebra)" title="Projection (linear algebra)">Projection</a></li>

<li><a href="Invertible_matrix" title="Invertible matrix">Invertible</a></li>

<li><a href="Involutory_matrix" title="Involutory matrix">Involutory</a></li>

<li><a href="Nilpotent_matrix" title="Nilpotent matrix">Nilpotent</a></li>

<li><a href="Normal_matrix" title="Normal matrix">Normal</a></li>

<li><a href="Orthogonal_matrix" title="Orthogonal matrix">Orthogonal</a></li>

<li><a href="Unimodular_matrix" title="Unimodular matrix">Unimodular</a></li>

<li><a href="Unipotent" title="Unipotent">Unipotent</a></li>

<li><a href="Unitary_matrix" title="Unitary matrix">Unitary</a></li>

<li><a href="Totally_unimodular_matrix" class="mw-redirect" title="Totally unimodular matrix">Totally unimodular</a></li>

<li><a href="Weighing_matrix" title="Weighing matrix">Weighing</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">With specific applications</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Adjugate_matrix" title="Adjugate matrix">Adjugate</a></li>

<li><a href="Alternating_sign_matrix" title="Alternating sign matrix">Alternating sign</a></li>

<li><a href="Augmented_matrix" title="Augmented matrix">Augmented</a></li>

<li><a href="B%C3%A9zout_matrix" title="Bézout matrix">Bézout</a></li>

<li><a href="Carleman_matrix" title="Carleman matrix">Carleman</a></li>

<li><a href="Cartan_matrix" title="Cartan matrix">Cartan</a></li>

<li><a href="Circulant_matrix" title="Circulant matrix">Circulant</a></li>

<li><a href="Cofactor_matrix" class="mw-redirect" title="Cofactor matrix">Cofactor</a></li>

<li><a href="Commutation_matrix" title="Commutation matrix">Commutation</a></li>

<li><a href="Confusion_matrix" title="Confusion matrix">Confusion</a></li>

<li><a href="Coxeter_matrix" class="mw-redirect" title="Coxeter matrix">Coxeter</a></li>

<li><a href="Distance_matrix" title="Distance matrix">Distance</a></li>

<li><a href="Duplication_and_elimination_matrices" title="Duplication and elimination matrices">Duplication and elimination</a></li>

<li><a href="Euclidean_distance_matrix" title="Euclidean distance matrix">Euclidean distance</a></li>

<li><a href="Fundamental_matrix_(linear_differential_equation)" title="Fundamental matrix (linear differential equation)">Fundamental (linear differential equation)</a></li>

<li><a href="Generator_matrix" title="Generator matrix">Generator</a></li>

<li><a href="Hessian_matrix" title="Hessian matrix">Hessian</a></li>

<li><a href="Householder_transformation" title="Householder transformation">Householder</a></li>

<li><a href="Jacobian_matrix_and_determinant" title="Jacobian matrix and determinant">Jacobian</a></li>

<li><a href="Moment_matrix" title="Moment matrix">Moment</a></li>

<li><a href="Payoff_matrix" class="mw-redirect" title="Payoff matrix">Payoff</a></li>

<li><a href="Random_matrix" title="Random matrix">Random</a></li>

<li><a href="Rotation_matrix" title="Rotation matrix">Rotation</a></li>

<li><a href="Routh%E2%80%93Hurwitz_matrix" title="Routh–Hurwitz matrix">Routh-Hurwitz</a></li>

<li><a href="Seifert_matrix" class="mw-redirect" title="Seifert matrix">Seifert</a></li>

<li><a href="Shear_matrix" class="mw-redirect" title="Shear matrix">Shear</a></li>

<li><a href="Similarity_matrix" class="mw-redirect" title="Similarity matrix">Similarity</a></li>

<li><a href="Symplectic_matrix" title="Symplectic matrix">Symplectic</a></li>

<li><a href="Totally_positive_matrix" title="Totally positive matrix">Totally positive</a></li>

<li><a href="Transformation_matrix" title="Transformation matrix">Transformation</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Used in <a href="Statistics" title="Statistics">statistics</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Centering_matrix" title="Centering matrix">Centering</a></li>

<li><a href="Correlation_matrix" class="mw-redirect" title="Correlation matrix">Correlation</a></li>

<li><a href="Covariance_matrix" title="Covariance matrix">Covariance</a></li>

<li><a href="Design_matrix" title="Design matrix">Design</a></li>

<li><a href="Doubly_stochastic_matrix" title="Doubly stochastic matrix">Doubly stochastic</a></li>

<li><a href="Fisher_information_matrix" class="mw-redirect" title="Fisher information matrix">Fisher information</a></li>

<li><a href="Precision_(statistics)" title="Precision (statistics)">Precision</a></li>

<li><a href="Stochastic_matrix" title="Stochastic matrix">Stochastic</a></li>

<li><a href="Stochastic_matrix" title="Stochastic matrix">Transition</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Used in <a href="Graph_theory" title="Graph theory">graph theory</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Adjacency_matrix" title="Adjacency matrix">Adjacency</a></li>

<li><a href="Biadjacency_matrix" class="mw-redirect" title="Biadjacency matrix">Biadjacency</a></li>

<li><a href="Degree_matrix" title="Degree matrix">Degree</a></li>

<li><a href="Edmonds_matrix" title="Edmonds matrix">Edmonds</a></li>

<li><a href="Incidence_matrix" title="Incidence matrix">Incidence</a></li>

<li><a href="Laplacian_matrix" title="Laplacian matrix">Laplacian</a></li>

<li><a href="Seidel_adjacency_matrix" title="Seidel adjacency matrix">Seidel adjacency</a></li>

<li><a href="Tutte_matrix" title="Tutte matrix">Tutte</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Used in science and engineering</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Cabibbo%E2%80%93Kobayashi%E2%80%93Maskawa_matrix" title="Cabibbo–Kobayashi–Maskawa matrix">Cabibbo–Kobayashi–Maskawa</a></li>

<li><a href="Density_matrix" title="Density matrix">Density</a></li>

<li><a href="Fundamental_matrix_(computer_vision)" title="Fundamental matrix (computer vision)">Fundamental (computer vision)</a></li>

<li><a href="Fuzzy_associative_matrix" title="Fuzzy associative matrix">Fuzzy associative</a></li>

<li><a href="Gamma_matrices" title="Gamma matrices">Gamma</a></li>

<li><a href="Hamiltonian_matrix" title="Hamiltonian matrix">Hamiltonian</a></li>

<li><a href="Irregular_matrix" title="Irregular matrix">Irregular</a></li>

<li><a href="Overlap_matrix" class="mw-redirect" title="Overlap matrix">Overlap</a></li>

<li><a href="State-transition_matrix" title="State-transition matrix">State transition</a></li>

<li><a href="Substitution_matrix" title="Substitution matrix">Substitution</a></li>

<li><a href="Z-matrix_(chemistry)" title="Z-matrix (chemistry)">Z (chemistry)</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Related terms</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Jordan_normal_form" title="Jordan normal form">Jordan normal form</a></li>

<li><a href="Linear_independence" title="Linear independence">Linear independence</a></li>

<li><a href="Matrix_exponential" title="Matrix exponential">Matrix exponential</a></li>

<li><a href="Matrix_representation_of_conic_sections" title="Matrix representation of conic sections">Matrix representation of conic sections</a></li>

<li><a href="Perfect_matrix" title="Perfect matrix">Perfect matrix</a></li>

<li><a href="Pseudoinverse" class="mw-redirect" title="Pseudoinverse">Pseudoinverse</a></li>

<li><a href="Row_echelon_form" title="Row echelon form">Row echelon form</a></li>

<li><a href="Wronskian" title="Wronskian">Wronskian</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div>

<ul><li><b><span class="nowrap"><span class="skin-invert-image noviewer" typeof="mw:File"></span> </span><a href="Portal%3AMathematics" title="Portal:Mathematics">Mathematics portal</a></b></li>

<li><a href="List_of_matrices" class="mw-redirect" title="List of matrices">List of matrices</a></li>

<li>Category:Matrices (mathematics)</li></ul>

</div></td></tr></tbody></table></div>

<div class="navbox-styles"></div><div role="navigation" class="navbox" aria-labelledby="Numerical_linear_algebra64" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Numerical_linear_algebra64" style="font-size:114%;margin:0 4em"><a href="Numerical_linear_algebra" title="Numerical linear algebra">Numerical linear algebra</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Key concepts</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Floating_point" class="mw-redirect" title="Floating point">Floating point</a></li>

<li><a href="Numerical_stability" title="Numerical stability">Numerical stability</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Problems</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="System_of_linear_equations" title="System of linear equations">System of linear equations</a></li>

<li><a href="Matrix_decomposition" title="Matrix decomposition">Matrix decompositions</a></li>

<li><a href="Matrix_multiplication" title="Matrix multiplication">Matrix multiplication</a> (<a href="Matrix_multiplication_algorithm" title="Matrix multiplication algorithm">algorithms</a>)</li>

<li><a href="Matrix_splitting" title="Matrix splitting">Matrix splitting</a></li>

</ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Hardware</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="CPU_cache" title="CPU cache">CPU cache</a></li>

<li><a href="Cache-oblivious_algorithm" title="Cache-oblivious algorithm">Cache-oblivious algorithm</a></li>

<li><a href="Multiprocessing" title="Multiprocessing">Multiprocessing</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Software</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Automatically_Tuned_Linear_Algebra_Software" title="Automatically Tuned Linear Algebra Software">ATLAS</a></li>

<li><a href="MATLAB" title="MATLAB">MATLAB</a></li>

<li><a href="Basic_Linear_Algebra_Subprograms" title="Basic Linear Algebra Subprograms">Basic Linear Algebra Subprograms (BLAS)</a></li>

<li><a href="LAPACK" title="LAPACK">LAPACK</a></li>

<li><a href="Comparison_of_linear_algebra_libraries" title="Comparison of linear algebra libraries">Specialized libraries</a></li>

<li><a href="Comparison_of_numerical-analysis_software" title="Comparison of numerical-analysis software">General purpose software</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-16" href="https://en.wikipedia.org/wiki/?title=Sparse_matrix&oldid=1300835532">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>